package study.sort1;

import java.util.Arrays;

public class BubboSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{5,8,6,3,9,2,1,7};
//        int[] arr = new int[]{5,6,1,7,8,9,10,11};
//        int[] arr = new int[]{3,4,2,1,5,6,7,8};
//        int[] arr = new int[]{2,3,4,5,6,7,8,1};
        int[] arr = new int[]{1,2,3,5,6,7,8,4};
//        int[] arr = new int[]{3,1,4,5,6,2,7,8};

//        sort(arr);
        cocktail(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * @param arr
     */
    static void sort(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        for (int i = 0, sorted = 0;;i ++) {
            int limit = arr.length - sorted - 1; // 无序和有序的分界的前一个元素（因为要比较j和j + 1)
            int maxSwapIndex = -1;
            for (int j = 0; j < limit; j++) {
                if(arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    maxSwapIndex = j;
                }
            }
            if(maxSwapIndex == -1) // 如果没有进行交换，说明是数组已经有序的，退出
                break;
            sorted = arr.length - maxSwapIndex - 1; // 已经有序的元素个数
            System.out.printf("第%d轮后：%s\n", i + 1, Arrays.toString(arr));
        }
    }

    /**
     * 鸡尾酒排序
     * @param arr
     */
    static void cocktail(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        int i = 0, j = arr.length - 1, count = 1;
        boolean flag = false;
        while(i < j) {
            boolean swap = false; // 是否交换了元素
            if(flag) { // 从右往左
                int lastSwapIndex = j; // 最后一次交换的元素索引
                for (int k = j; k > i; k--) {
                    if(arr[k - 1] > arr[k]) {
                        int t = arr[k];
                        arr[k] = arr[k - 1];
                        arr[k - 1] = t;
                        swap = true;
                        lastSwapIndex = k;
                    }
                }
                i = lastSwapIndex;
            } else { // 从左往右
                int lastSwapIndex = i; // 最后一次交换的元素索引
                for (int k = i; k < j; k++) {
                    if(arr[k] > arr[k + 1]) {
                        int t = arr[k];
                        arr[k] = arr[k + 1];
                        arr[k + 1] = t;
                        swap = true;
                        lastSwapIndex = k;
                    }
                }
                j = lastSwapIndex;
            }
            if(!swap) // 如果没有交换元素
                break;
            flag = !flag;
            System.out.printf("第%d轮后：%s\n", count ++, Arrays.toString(arr));
        }
    }
}
